package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC91 {

    public int numDecodings(String s) {
        if (s.length() == 0) {
            return 0;
        }

        /**
         * 字符串长度为1的情况
         */
        int[] dp = new int[s.length()];
        dp[0] = s.charAt(0) == '0' ? 0 : 1;
        if (s.length() == 1) {
            return dp[0];
        }

        /**
         * 字符串长度>=2，第一种是拆分的情况，第二种是合并的情况
         * 在进行DP的时候还需要考虑几种特殊的情况：
         （1）当前位置i的字符为’0’，那么不能考虑单独一位，只能考虑合并
         （2）当前位置和前面的位置合并的时候>‘26’，那么只能考虑单独一位
         */
        dp[1] += s.charAt(0) > '0' && s.charAt(1) > '0' ? 1 : 0;//第一种是独立的情况，有一个为0，就不能拆分了1-0这样子
        dp[1] += (s.charAt(0) == '1' || s.charAt(0) == '2' && s.charAt(1) <= '6' ? 1 : 0);//这一种是合并的情况

        for (int i = 2; i < s.length(); i++) {
            /**
             * 当前位置i，能否独立
             */
            if (s.charAt(i) != '0') {
                dp[i] += dp[i - 1];
            }
            /**
             * 当前位置i，能否合并
             */
            if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2' && s.charAt(i) <= '6') {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length() - 1];
    }

    public static void main(String[] args) {
        LC91 an = new LC91();
        System.out.println(an.numDecodings("12345"));;
    }
}
